import sortedcontainers
class Node:
    def __init__(self, val, prev=None, suff=None):
        self.val = val
        self.prev = prev
        self.suff = suff


class MaxStack(object):

    def __init__(self):
        self.order = sortedcontainers.SortedList(key=lambda x: x.val)
        self.count = 0
        self.end = None

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        node = Node(x)
        self.order.add(node)
        if self.count == 0:
            self.end = node
        else:
            self.end.suff = node
            node.prev = self.end
        self.end = node
        self.count += 1

    def pop(self):
        """
        :rtype: int
        """
        node = self.end
        self.order.remove(node)
        prev_node = node.prev
        if prev_node:
            prev_node.suff = None
        self.end = prev_node
        self.count -= 1
        return node.val

    def top(self):
        """
        :rtype: int
        """
        return self.end.val

    def peekMax(self):
        """
        :rtype: int
        """
        return self.order[-1].val

    def popMax(self):
        """
        :rtype: int
        """
        node = self.order.pop()
        prev_node = node.prev
        suff_node = node.suff
        if prev_node:
            prev_node.suff = suff_node
        if suff_node:
            suff_node.prev = prev_node
        if node == self.end:
            self.end = prev_node
        self.count -= 1
        return node.val


obj = MaxStack()
obj.push(5)
obj.push(1)
obj.push(5)
